package com.test.daily.leetcode.y2022.m05.day0529.v01;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/29 下午 02:25
 * @version: 1.0
 */
public class Code03_TopologicalOrderBFS {
    public static class DirectedGraphNode{
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode(int x){
            this.label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }

        public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph){
                HashMap<DirectedGraphNode, Integer> indegreeMap = new HashMap<>();
                Queue<DirectedGraphNode> zeroQueue = new LinkedList<>();
                for(DirectedGraphNode cur: graph){
                    indegreeMap.put(cur, 0);
                }
                for (DirectedGraphNode cur: graph){
                    for (DirectedGraphNode next: cur.neighbors){
                        indegreeMap.put(next, indegreeMap.get(next) + 1);
                    }
                }
                for(DirectedGraphNode cur: indegreeMap.keySet()){
                    if(indegreeMap.get(cur) == 0){
                        zeroQueue.add(cur);
                    }
                }
                ArrayList<DirectedGraphNode> ans = new ArrayList<>();
                while (!zeroQueue.isEmpty()){
                    DirectedGraphNode cur = zeroQueue.poll();
                    ans.add(cur);
                    for(DirectedGraphNode neighbor: cur.neighbors){
                        indegreeMap.put(neighbor, indegreeMap.get(neighbor) - 1);
                        if(indegreeMap.get(neighbor) == 0){
                            zeroQueue.offer(neighbor);
                        }
                    }
                }
                return ans;
        }
    }
}
